Let $A$ and $B$ be disjoint sets, of size $2^k$, of vertices of $Q_n$, the$n$-dimensional hypercube. In 1997, Bollob\'as and Leader proved that theremust be $(n-k)2^k$ edge-disjoint paths between such $A$ and $B$. Theyconjectured that when $A$ is a down-set and $B$ is an up-set, these paths maybe chosen to be directed (that is, the vertices in the path form a chain). Weuse a novel type of compression argument to prove stronger versions of theseconjectures, namely that the largest number of edge-disjoint paths between adown-set $A$ and an up-set $B$ is the same as the largest number of directededge-disjoint paths between $A$ and $B$. Bollob\'as and Leader made ananalogous conjecture for vertex-disjoint paths and we prove a strengthening ofthis by similar methods. We also prove similar results for all other sizes of$A$ and $B$.
展开▼
机译：假设$ A $和$ B $是大小为$ 2 ^ k $的不相交集合，其顶点为$ Q_n $维，即$ n $维超立方体。 1997年，Bollob'as和Leader证明，在这样的$ A $和$ B $之间必须存在$（n-k）2 ^ k $边不相交的路径。他们推测，当$ A $是向下位移而$ B $是向上位移时，可以选择将这些路径定向（即，路径中的顶点形成一条链）。我们使用一种新颖的压缩自变量来证明这些猜想的更强形式，即，向下的$ A $和向上的$ B $之间的最大边不相交路径与最大有向边不相交的数量相同$ A $和$ B $之间的路径。 Bollob'as和Leader提出了顶点不相交路径的类似猜想，我们通过相似的方法证明了这一点的增强。对于$ A $和$ B $的所有其他大小，我们也证明了相似的结果。
展开▼
